package com.mystudy.leetcode.problem.link.p_160;

import com.mystudy.leetcode.base.ListNode;
import org.apache.http.client.methods.HttpExecutionAware;
import org.junit.Test;

/**
 * @program: infoalgorithm
 * @description: 找出相交链表的链接点
 * @author: zhouzhilong
 * @create: 2019-07-04 11:02
 **/
public class Solution {


    /**
     * 循环
     * 事件复杂度O(n2)
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode intersection = null;
        for (ListNode cura = headA; cura != null && intersection == null; cura = cura.next) {
            for (ListNode curb = headB; curb != null; curb = curb.next) {
                if (cura == curb) {
                    intersection = cura;
                    break;
                }
            }
        }
        return intersection;
    }


    /**
     * 由于O(n2)的效率实在太低,所以要想办法让两个链表从距离末尾同等距离的位置开始遍历,就是O(n)了
     */

    // A、B指针分别指向两个链表的头节点，令A、B依次向后加，
    // 若到达自身链表末尾，则指向另外一个链表的头节点，继续向后加，
    // 若A和B相等，且不为NULL，则此时处于两链表首个交点处
    // 若到达另外一个链表末尾前，A和B未曾相等，则说明两链表无交点。
    //
    // 证明：
    // 假设，链表A相交前有m个结点，B相交前有n个结点，两链表相交后至末尾有k个结点；
    // 指针从A链表头开始，向后加至A末尾，再指向B链表头，向后加至首个相交结点处，共走了m+k+n步；
    // 同理，指针从B链表投开始，到最后相交，共走了n+k+m步，和从A出发的指针所走步数一致；
    // 因此，若A链表和B链表相交，则这样走当两指针相等时必然是在首个相交结点处。
    // 若A链表和B链表不相交，则两指针会在走了m+n步后同时走到对方链表末尾，均变为NULL。
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode cura = headA;
        ListNode curb = headB;

        while (cura != curb) {
            if (cura == null) {
                cura = headB;
            } else {
                cura = cura.next;
            }

            if (curb == null) {
                curb = headA;
            } else {
                curb = curb.next;
            }

        }
        return cura;
    }


}
